package com.salim.leetcode.$22;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        StringBuilder str = new StringBuilder();
        str.append("(");
        loop(n-1,str,1,result);
        return result;
    }

    public void loop(int n,StringBuilder str,int unCloseNum,List<String> result){
        if(n==0){
            if(unCloseNum==0){
                result.add(str.toString());
            }else{
                StringBuilder newStr = new StringBuilder(str);
                newStr.append(")");
                loop(n,newStr,unCloseNum-1,result);
            }
        }else{
            if(unCloseNum==0){
                StringBuilder newStr = new StringBuilder(str);
                newStr.append("(");
                loop(n-1,newStr,unCloseNum+1,result);
            }else{
                StringBuilder newStr = new StringBuilder(str);
                newStr.append("(");
                loop(n-1,newStr,unCloseNum+1,result);
                StringBuilder newStr2 = new StringBuilder(str);
                newStr2.append(")");
                loop(n,newStr2,unCloseNum-1,result);
            }
        }
    }

    public static void main(String[] args){
        GenerateParenthesis generateParenthesis = new GenerateParenthesis();
        System.out.println(generateParenthesis.generateParenthesis(3));
    }
}
